package com.zlk.algorithm.dataStructure.linkList03;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName FindFirstIntersectSimpleNode
 * @description: 查找第一个相交节点
 * 可能性分析
 * 1、两个链表无环
 * 2、一个链表有环一个链表无环（这种情况不可能有交点）
 * 3、两个都有环
 * @author: slfang
 * @create: 2024-02-02 08:51
 * @Version 1.0
 **/
public class Code10_FindFirstIntersectNode {
    //1、实现函数判断链表是否有环
    //2、a:一个有环一个无环  b:都有环   c:都无环

    @Test
    public void test(){
        SimpleNode head1 = new SimpleNode(1);
        head1.next = new SimpleNode(2);
        head1.next.next = new SimpleNode(3);
        head1.next.next.next = new SimpleNode(4);
        head1.next.next.next.next = new SimpleNode(5);
        head1.next.next.next.next.next = new SimpleNode(6);
        head1.next.next.next.next.next.next = new SimpleNode(7);
        //System.out.println(isLoopList(head1));
        // 0->9->8->6->7->null
        SimpleNode head2 = new SimpleNode(0);
        head2.next = new SimpleNode(9);
        head2.next.next = new SimpleNode(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        //System.out.println(isLoopList(head2));

        // 1->2->3->4->5->6->7->4...
        head1 = new SimpleNode(1);
        head1.next = new SimpleNode(2);
        head1.next.next = new SimpleNode(3);
        head1.next.next.next = new SimpleNode(4);
        head1.next.next.next.next = new SimpleNode(5);
        head1.next.next.next.next.next = new SimpleNode(6);
        head1.next.next.next.next.next.next = new SimpleNode(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
        System.out.println(isLoopList(head1));

        // 0->9->8->2...
        head2 = new SimpleNode(0);
        head2.next = new SimpleNode(9);
        head2.next.next = new SimpleNode(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(isLoopList(head2));

        // 0->9->8->6->4->5->6..
        head2 = new SimpleNode(0);
        head2.next = new SimpleNode(9);
        head2.next.next = new SimpleNode(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(isLoopList(head2));
    }


    /**
     * 利用快慢指针来判断
     * @param SimpleNode
     * @return
     */
    boolean isLoopList(SimpleNode SimpleNode){
        if(SimpleNode==null||SimpleNode.next==null){
            return false;
        }
        SimpleNode slowSimpleNode = SimpleNode;
        SimpleNode fastSimpleNode = SimpleNode.next;
        while ((fastSimpleNode!=null&&fastSimpleNode.next!=null)){
            if(slowSimpleNode.value==fastSimpleNode.value){
                return true;
            }
            slowSimpleNode = slowSimpleNode.next;
            fastSimpleNode = fastSimpleNode.next.next;
        }
        return false;
    }


    // 方法1 可以用HashSet 容器方法
    //直接记这个流程 不用管流程
    // 首先快慢指针相遇
    // 然后f 回到原来head 位置
    // 然后s1步  f一步
    // 然后一定会在环的第一个节点相遇
    SimpleNode getFirstLoopNode(SimpleNode head){
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        SimpleNode slow = head.next;
        SimpleNode fast = head.next.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    /**
     *
     * @param node1
     * @param node2
     * @return
     */
//    public SimpleNode FindFirstIntersectNode(SimpleNode node1,SimpleNode node2){
//        SimpleNode loopNode1 = getFirstLoopNode(node1);
//        SimpleNode loopNode2 = getFirstLoopNode(node2);
//        if(loopNode1==null){
//            //都无环
//            return noLoop(node1,node2);
//        }else if(){
//
//        }
//
//
//    }

    //无环操作
    //
    //  相交只会两种情况  Y型 和 |  不可能到Y型（一个节点不可能有两个next节点）
    //  所以如果两个链表相交最后一个节点一定相等
    //  怎么找到交点 得取到 两个长度得差值，然后长得链表先走差值长度，然后 cur1  cur2 分别开始一起走，看哪个地方重合就是第一个交点
    //
    private SimpleNode noLoop(SimpleNode node1, SimpleNode node2) {
        if (node1 == null || node2 == null) {
            return null;              //         |
        }
        SimpleNode cur1 = node1;
        SimpleNode cur2 = node2;
        int n1 = 0;
        int n2 = 0;
        while (cur1!=null){
            n1++;
            cur1 = cur1.next;
        }
        while (cur2!=null){
            n2++;
            cur2 = cur2.next;
        }
        if(cur1!=cur2){
            return null;
        }
        cur1 = n1>=n2?node1:node2;
        cur2 = n2>n1?node2:node1;
        int diff =Math.abs(n1-n2);
        if(diff==0){//node1 == node2
            return node1;
        }else{
            while (diff!=0){
                cur1 = cur1.next;
                diff--;
            }
            while (cur1!=cur2){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }
    }


}
